// @algorithm @lc id=1463 lang=cpp 
// @title the-k-weakest-rows-in-a-matrix


// @test([[1,1,0,0,0],[1,1,1,1,0],[1,0,0,0,0],[1,1,0,0,0],[1,1,1,1,1]],3)=[2,0,3]
// @test([[1,0,0,0],[1,1,1,1],[1,0,0,0],[1,0,0,0]],2)=[0,2]
class Solution {
public:
    vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
        // 二分查找 0 的index，即1的个数
        function<int(vector<int>)> bs0 = [&](vector<int> ln){
            int b = 0, e = (int)ln.size();
            while(b < e){
                auto m = b + (e-b)/2;
                ln[m] ? b=m+1 : e = m;
            }
            return b;
        };
        // multimap<1的个数, matIdx>
        multimap<int,int> cnt;
        for(int i=0; i<(int)mat.size(); i++)
            cnt.insert({bs0(mat[i]), i});
        // 取最小 k 个
        vector<int> ans;
        ans.reserve(k);
        for(auto &[n,i] : cnt){
            ans.push_back(i);
            if(ans.size()==k)break;
        }
        return ans;
    }
};